(1) Field of Invention
The present invention relates to a method for secure pattern matching and, more particularly, to a method for secure pattern matching using homomorphic properties of encryption.
(2) Description of Related Art
In computer science, pattern matching is the act of checking some sequence of characters from a fixed alphabet for the presence of the constituents of some pattern. The patterns generally have the form of a sequence of characters. Pattern matching has many applications in computer science including, but not limited to, text-processing, database operations, network filtering, and security applications. It is a problem that has been extensively researched, resulting in several efficient (although insecure) techniques to solve various variations thereof. Prior art schemes for secure pattern matching fall into three groups: ones that rely on homomorphic operations (see the List of Cited Literature References, Literature Reference No. 15), generic methods in secure multiparty computation (see Literature Reference No. 17), or secure finite state machines (FSM) evaluation (see Literature Reference Nos. 2, 11 and 25).
The main disadvantage of the prior art, such as in Literature Reference No. 17, is that it does not efficiently support wildcard match, substring matching, or support the stronger malicious security model. Existing secure pattern matching techniques that depend on securely evaluating FSM (see Literature References No. 2, 11, and 25) require a number of interaction rounds between client and server which are proportional to the number of states in the FSM. This significantly limits the size of FSM that can be evaluated and greatly increases the number of rounds of interaction between client and server. It also renders the usage of wildcards problematic, because they cause a quadratic explosion in the number of states.
Troncoso-Pastoriza, Katzenbeisser, and Celik (see Literature Reference No. 25) developed a secure pattern matching protocol for deoxyribonucleic acid (DNA) analysis by employing oblivious evaluation of automata. The total computation, bandwidth and number of rounds, is linear in n, and their protocol is only secure in the honest-but curious model. Hazay and Lindel (see Literature Reference No. 13) relied on oblivious pseudorandom function (OPRF) evaluation to construct a protocol to perform secure exact pattern matching. Their protocol only achieves a security notion called one-sided simulation, which doesn't model malicious behavior for both the parties. On the other hand, Gennaro et al. (see Literature Reference No. 11) created a secure exact matching scheme in the static malicious model, but they required O(nm) computation and bandwidth complexity.
Katz and Malka (see Literature Reference No. 17) recently proposed a protocol for a generalized pattern matching problem (text processing). In text processing, the party holding the pattern has some additional information, y, and the goal is to learn a function of the text and y for the text locations where p is a substring of the text. Their protocol does not support substring matching or single character wildcards and achieves only one-sided simulation. Their main contribution is to construct a garbled circuit (see Literature Reference No. 27) with size depending on an upper bound of the number of occurrences of the pattern in the text rather than the entire length of the text.
Thus, a continuing need exists for a secure pattern matching method that is efficient in both its speed and memory usage, can handle wildcards, and approximate matches.